package com.itheima.window;

public class LeetCode3439 {
    //给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。
    //
    //同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。
    //
    //你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。
    //
    //移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。
    //
    //请你返回重新安排会议以后，可以得到的 最大 空余时间。
    //
    //注意，会议 不能 安排到整个活动的时间以外。
    //思路：将思维转为移动空闲时间，k次移动机会足以将k+1个空闲时间拼在一起(截断一条绳子的n个切口切出11段)，因此窗口大小为k+1，先将空闲时间记录在一个数组。
    //总结：将问题转换成移动窗口

    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[] times = new int[n + 1];
        int max = 0;
        int sum = 0;

        //将空闲时间变成数字存储在数组中
        //最左数据
        times[0] = startTime[0];
        //中间数据
        for (int i = 1; i < n; i++) {
            times[i] = startTime[i] - endTime[i - 1];
        }
        //最右数据
        times[n] = eventTime - endTime[n - 1];

        //开始移动窗口
        for (int i = 0; i < (n + 1); i++) {
            sum += times[i];
            if(i < k){
                continue;
            }
            max = Math.max(max, sum);
            sum -= times[i - k];
        }
        return max;
    }
}
